class DSU:
    def __init__(self):
        self.parent = {}

    def find(self, node):
        if node not in self.parent:
            self.parent[node] = node
            return node
        if node == self.parent[node]:
            return node
        else:
            nodeParent = self.parent[node]
            self.parent[node] = self.find(nodeParent)
            return self.parent[node]

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        self.parent[yp] = xp


class Solution:
    def minimumHammingDistance(self, source: list, target: list,
                               allowedSwaps: list) -> int:
        dsu = DSU()
        for allowedSwap in allowedSwaps:
            dsu.union(allowedSwap[0], allowedSwap[1])
        m = {}
        for i in range(len(source)):
            p = dsu.find(i)
            if p not in m:
                m[p] = []
            m[p] += [i]
        res = 0
        for key in m.keys():
            t = {}
            for i in m[key]:
                if target[i] not in t:
                    t[target[i]] = 0
                t[target[i]] += 1
            for i in m[key]:
                if source[i] in t:
                    t[source[i]] -= 1
                    if t[source[i]] == 0:
                        del t[source[i]]
            for v in t.values():
                res += v

        return res


if __name__ == '__main__':
    print(Solution().minimumHammingDistance(source=[1, 2, 3, 4],
                                            target=[2, 1, 4, 5],
                                            allowedSwaps=[[0, 1], [2, 3]]))
    print(Solution().minimumHammingDistance(source=[1, 2, 3, 4],
                                            target=[1, 3, 2, 4],
                                            allowedSwaps=[]))
    print(Solution().minimumHammingDistance(source=[5, 1, 2, 4, 3],
                                            target=[1, 5, 4, 2, 3],
                                            allowedSwaps=[[0, 4], [4, 2],
                                                          [1, 3], [1, 4]]))
